//题目:
// 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。
// 地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
// 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
// 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；
// 其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
// 为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
// 返回确保骑士能够拯救到公主所需的最低初始健康点数。
// 注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
#include<iostream>
#include<limits.h>
#include<vector>
#include<map>

using namespace std;
//代码
class Solution 
{
    int ret=INT_MIN;
    //行路过程中，骑士健康点最低值
    int dx[2]={0,1},dy[2]={1,0};
    map<pair<int,int>,int> dp;//记录从(i,j)位置到终点，骑士健康点最低值
public:
    //全排列
    void dfs(const vector<vector<int>>& dungeon,int row,int col,int sum,int tmp_min)
    {   
        tmp_min=min(tmp_min,sum+dungeon[row][col]);

        if(row==dungeon.size()-1 && col==dungeon[0].size()-1){
            ret=max(ret,tmp_min);//骑士健康点最低值中最高的那个
            return;
        }
        //寻找下一个落脚点
        for(int i=0;i<2;i++)
        {
            int x=row+dx[i],y=col+dy[i];
            if(x>=0 && x<dungeon.size() && y>=0 && y<dungeon[0].size())
            {
                dfs(dungeon,x,y,sum+dungeon[row][col],tmp_min);
            }
        }
    }
    int calculateMinimumHP(vector<vector<int>>& dungeon) 
    {
        //法一：全排列
        // dfs(dungeon,0,0,0,INT_MAX);
        // return ret>=0?1:1-ret;

        //法二：记忆化搜索     × 
        // int ret=dfs(dungeon,0,0,0);
        // return ret>=0?1:1-ret;

        //法三:动态规划
        //1.创建vv表————记录从(i,j)位置到终点，骑士健康点最低值    ×
        // int m=dungeon.size(),n=dungeon[0].size();
        // vector<vector<int>> vv(m,vector<int>(n));//记录从初始位置到(i,j)位置，骑士健康点最低值 
        // vector<vector<int>> dp(m,vector<int>(n));//记录从初始位置到(i,j)位置路径最小值
        // //2.初始化
        // dp[0][0]=dungeon[0][0];
        // for(int i=1;i<m;i++)
        //     dp[i][0]=dp[i-1][0]+dungeon[i][0];
        // for(int j=1;j<n;j++)
        //     dp[0][j]=dp[0][j-1]+dungeon[0][j];

        // vv[0][0]=dungeon[0][0];
        // for(int i=1;i<m;i++)
        // {
        //     if(dungeon[i][0]>0) vv[i][0]=vv[i-1][0];
        //     else vv[i][0]=min(vv[i-1][0],dungeon[i][0]+dp[i-1][0]);
        // }
        // for(int j=1;j<n;j++)
        // {
        //     if(dungeon[0][j]>0) vv[0][j]=vv[0][j-1];
        //     else vv[0][j]=min(vv[0][j],dungeon[0][j]+dp[0][j-1]);
        // }
        // //3.填表
        // for(int i=1;i<m;i++)
        // {
        //     for(int j=1;j<n;j++)
        //     {
        //         int on_min=vv[i-1][j],left_min=vv[i][j-1];
        //         if(dungeon[i][j]<0)
        //         {
        //             if(dungeon[i][j]+dp[i-1][j]<vv[i-1][j])
        //                 on_min=dungeon[i][j]+dp[i-1][j];
        //             if(dungeon[i][j]+dp[i][j-1]<vv[i][j-1])
        //                 left_min=dungeon[i][j]+dp[i][j-1];
        //         }
        //         if(left_min>on_min)
        //         {
        //             vv[i][j]=left_min;
        //             dp[i][j]=dungeon[i][j]+vv[i][j-1];
        //         }
        //         else
        //         {
        //             vv[i][j]=on_min;
        //             dp[i][j]=dungeon[i][j]+dp[i-1][j];
        //         }
        //     }
        // }
        //4.确定返回值
        // int health_min=vv[m-1][n-1];
        // return health_min>=0?1:1-health_min;

        //动态规划
        //1.创建dp表————记录从(i,j)位置到终点，骑士健康点最低值
        int m=dungeon.size(),n=dungeon[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        //2.初始化
        dp[m][n-1]=dp[m-1][n]=1;
        //3.填表
        for(int i=m-1;i>=0;i--)
        {
            for(int j=n-1;j>=0;j--)
            {
                dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                dp[i][j]=max(1,dp[i][j]);
            }
        }
        //4.返回值
        return dp[0][0];
    }
};